package com.leetCode.ListNodeDemo;

import java.util.ArrayList;
import java.util.List;

public class ReverseKGroupDemo {
    public static void main(String[] args) {
        ListNode twoNode1 = new ListNode(1);
        ListNode twoNode2 = new ListNode(2);
        ListNode twoNode3 = new ListNode(3);
        ListNode twoNode4 = new ListNode(4);
        ListNode twoNode5 = new ListNode(5);
        twoNode1.next = twoNode2;
        twoNode2.next = twoNode3;
        twoNode3.next = twoNode4;
        twoNode4.next = twoNode5;
        System.out.println(reverseKGroup1(twoNode1,2));
    }

    /**
     * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
     *
     * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     *
     * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
     *
     * 示例 1：
     *
     *
     * 输入：head = [1,2,3,4,5], k = 2
     * 输出：[2,1,4,3,5]
     * 示例 2：
     *
     *
     *
     * 输入：head = [1,2,3,4,5], k = 3
     * 输出：[3,2,1,4,5]
     * 提示：
     * 链表中的节点数目为 n
     * 1 <= k <= n <= 5000
     * 0 <= Node.val <= 1000
     * 进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1){
            return head;
        }
        List<Integer> valueList = new ArrayList<>();
        ListNode tempNode = head;
        while (tempNode != null){
            valueList.add(tempNode.val);
            tempNode = tempNode.next;
        }
        //按照k分割数据
        int rate = valueList.size() / k;
        if (rate > 0){
            ListNode rootNode = new ListNode();
            ListNode swapNode = null;
            for (int i = 0;i < rate;i++){
                int count = (i + 1) * k - 1;
                //循环k次
                for (int j = 0;j < k;j++){
                    ListNode newNode = new ListNode(valueList.get(count--));
                    if (swapNode == null){
                        rootNode.next = newNode;
                    } else {
                        swapNode.next = newNode;
                    }
                    swapNode = newNode;
                }
            }
            //不足k倍的节点按照原顺序写入
            for (int s = rate * k;s < valueList.size();s++){
                ListNode otherNode = new ListNode(valueList.get(s));
                swapNode.next = otherNode;
                swapNode = otherNode;
            }
            return rootNode.next;
        }
        return head;
    }

    /**
     * 使用固定大小集合处理
     */
    public static ListNode reverseKGroup1(ListNode head, int k) {
        if (head == null || k == 1){
            return head;
        }
        List<ListNode> valueList = new ArrayList<>(k);
        ListNode rootNode = new ListNode();
        ListNode swapNode = null;
        int count = 1;
        while (head != null){
            ListNode nextNode = head.next;
            valueList.add(head);
            //每k次,从来集合中取值,拼接数据
            if (count == k){
                //k大小集合反转情况处理
                for (int i = valueList.size() - 1;i >= 0;i--){
                    ListNode newNode = valueList.get(i);
                    newNode.next = null;
                    if (swapNode == null){
                        rootNode.next = newNode;
                    } else {
                        swapNode.next = newNode;
                    }
                    swapNode = newNode;
                }
                count = 0;
                valueList.clear();
            } else {
                //不足k个节点数，直接去末尾元素数据
                if (nextNode == null){
                    if (swapNode == null){
                        rootNode.next = valueList.get(0);
                    } else {
                        swapNode.next = valueList.get(0);
                    }
                }
            }
            count++;
            head = nextNode;
        }
        return rootNode.next;
    }
}
